Return to the table of contents
Like any complex tool, the computer can be understood on several levels. For example, it's entirely possible to learn to drive an automobile without having the slightest idea of how it works. The analogy with computers is that it's relatively easy to learn how to use a word processor without having any notion of how such programs work. On the other hand, programming is much more closely analogous to designing an automobile than it is to driving one; therefore, we're going to have to go into some detail about the internal workings of a computer, not at the level of electronic components, but at the lowest level accessible to a programmer. This is a book on learning to program in C++, not on how a computer works.1 Therefore, it might seem better to start there and eliminate this detour, and indeed many (perhaps most) books on C++ do exactly that. However, in working out in detail how I'm going to explain C++ to you, I've come to the conclusion that it would be virtually impossible to explain why certain features of the language exist and how they actually work, without your understanding how they relate to the underlying computer hardware.
I haven't come to this position by pure logical deduction, either. In fact, I've worked backward from the concepts that you will need to know to program in C++ to the specific underlying information that you will have to understand first. I'm thinking in particular of one specific concept that is supposed to be extremely difficult for a beginning programmer in C++ to grasp. With the approach we're taking, you shouldn't have much trouble understanding this concept by the time you get to it in Chapter string.htm; it's noted as such in the discussion there. I'd be interested to know how you find my explanation there, given the background that you'll have by that point; don't hesitate to e-mail me about this topic (or any other, for that matter).2 On the other hand, if you're an experienced programmer, a lot of this will be just review for you. Nonetheless, it can't hurt to go over the basics one more time before diving into the ideas and techniques that make C++ different from other languages.
Now let's begin with some definitions and objectives for this chapter.
A digit is one of the characters used in any positional numbering system to represent all numbers starting at 0 and ending at one less than the base of the numbering system. In the decimal system, there are ten digits, 0 through 9, and in the hexadecimal system there are sixteen digits, 0 through 9 and a through f.
A binary number system is one that uses only two digits, 0 and 1.
A hexadecimal number system is one that uses 16 digits, 0-9 and a-f.
CPU is an abbreviation for Central Processing Unit. This is the "active" part of your computer, which executes all the machine instructions that make the computer do useful work.
A machine instruction is one of the fundamental operations that a CPU can perform. Some examples of these operations are addition, subtraction, or other arithmetic operations; other possibilities include operations that control what instruction will be executed next. All C++ programs must be converted into machine instructions by a compiler before they can be executed by the CPU.
An assembly language program is the human-readable representation of a set of machine instructions; each assembly language statement corresponds to one machine instruction. By contrast, a C++ program consists of much higher-level operations which cannot be directly translated one-for-one into machine instructions.
By the end of this chapter, you should
First we'll need to expand on the definition of hardware. As noted earlier, hardware means the physical components of a computer, the ones you can touch.3 Examples are the monitor, which displays your document while you're working on it, the keyboard, the printer, and all of the interesting electronic and electromechanical components inside the case of your computer.4 Right now, we're concerned with the programmer's view of the hardware. The hardware components of a computer with which you'll be primarily concerned are the disk, RAM (short for Random Access Memory), and last but certainly not least, the CPU (short for Central Processing Unit).5 We'll take up each of these topics in turn.
When you sit down at your computer in the morning, before you turn it on, where are the programs you're going to run? To make this more specific, suppose you're going to use a word processor to revise a letter you wrote yesterday before you turned the computer off. Where is the letter, and where is the word processing program?
You probably know the answer to this question; they are stored on a disk inside the case of your computer.6 Disks use magnetic recording media, much like the material used to record speech and music on cassette tapes, to store information in a way that will not be lost when the power is turned off. How exactly is this information (which may be either executable programs or data such as word processing documents) stored?
We don't have to go into excruciating detail on the storage mechanism, but it is important to understand some of its characteristics. A disk consists of one or more circular platters, which are extremely flat and smooth pieces of metal or glass covered with a material that can be very rapidly and accurately magnetized in either of two directions, "north" and "south". To store large amounts of data, each platter is divided into many millions of small regions, each of which can be magnetized in either direction independent of the other regions. The magnetization is detected and modified by recording heads, similar in principle to those used in tape cassette decks. However, in contrast to the cassette heads, which make contact with the tape while they are recording or playing back music or speech, the disk heads "fly" a few millionths of an inch away from the platters, which rotate at very high velocity.7 The separately magnetizable regions used to store information are arranged in groups called sectors, which are in turn arranged in concentric circles called tracks. All tracks on one side of a given platter (a recording surface) can be accessed by a recording head dedicated to that recording surface; each sector is used to store some number of bytes of the data, generally a few hundred to a few thousand. "Byte" is a coined word meaning a group of 8 binary digits, or bits for short.8 You may wonder why the data aren't stored in the more familiar decimal system, which of course uses the digits from 0 through 9. This is not an arbitrary decision; on the contrary, there are a couple of very good reasons that data on a disk are stored using the binary system, in which each digit has only two possible states, 0 and 1. One of these reasons is that it's a lot easier to determine reliably whether a particular area on a disk is magnetized "north" or "south" than it is to determine 1 of 10 possible levels of magnetization. Another reason is that the binary system is also the natural system for data storage using electronic circuitry, which is used to store data in the rest of the computer.
While magnetic storage devices have been around in one form or another since the very early days of computing, the advances in technology just in the last 10 years have been staggering. To comprehend just how large these advances have been, we need to define the term used to describe storage capacities: the Megabyte. The standard engineering meaning of Mega is "multiply by 1 million", which would make a Megabyte equal to 1 million (1,000,000) bytes. As we have just seen, however, the natural number system in the computer field is binary. Therefore, "one Megabyte" is often used instead to specify the nearest "round" number in the binary system, which is 2^20 (2 to the 20th power), or 1,048,576 bytes.9 This wasn't obvious to Susan, so I explained it some more, as you can see here:
Susan: Just how important is it to really understand that the Megabyte is 2^20 (1,048,576) bytes? I know that a meg is not really a meg; that is, it's more than a million. But I don't understand 2^20, so is it enough to just take your word on this and not get bogged down as to why I didn't go any further than plane geometry in high school? You see, it makes me worry and upsets me that I don't understand how you "round" a binary number.
Steve: The ^ symbol is a common way of saying "to the power of", so 2^20 would be 2 to the power of 20; that is, 20 2s multiplied together. This is a "round" number in binary just as 10 * 10 * 10 (1000) is a "round" number in decimal.
With that detail out of the way, we can see just how far we've come in a short period of time. In 1985, I purchased a 20 Megabyte disk for $900 ($45 per Megabyte); its access time, which measures how long it takes to retrieve data, was approximately 100 milliseconds (milli = 1/1000, so a millisecond is one thousandth of a second). In April 1997, a 6510 Megabyte disk cost as little as $449, or approximately 7 cents per Megabyte; in addition to delivering 650 times as much storage per dollar, this disk had an access time of 14 milliseconds, which is approximately 7 times as fast as the old disk. Of course, this significantly understates the amount of progress in technology in both economic and technical terms. For one thing, a 1997 dollar is worth considerably less than a 1985 dollar. In addition, the new drive is superior in every other measure as well: It is much smaller than the old one, consumes much less power, and has many times the projected reliability of the old drive.
This tremendous increase in performance and price has prevented the long-predicted demise of disk drives in favor of new technology. However, the inherent speed limitations of disks still require us to restrict their role to the storage and retrieval of data for which we can afford to wait a relatively long time.
You see, while 14 milliseconds isn't very long by human standards, it is a long time indeed to a modern computer. This will become more evident as we examine the next essential component of the computer, the RAM.
The working storage of the computer, where data and programs are stored while we're using them is called RAM, which is an acronym for Random Access Memory.10 For example, your word processor is stored in RAM while you're using it. The document you're working on is likely to be there as well unless it's too large to fit all at once, in which case parts of it will be retrieved from the disk as needed. Since we have already seen that both the word processor and the document are stored on the disk in the first place, why not leave them there and use them in place, rather than copying them into RAM?
The answer, in a word, is speed. RAM is physically composed of millions of microscopic switches on a small piece of silicon known as a chip: a 4 megabit RAM chip has approximately 4 million of them.11 Each of these switches can be either on or off; we consider a switch that is "on" to be storing a 1, and a switch that is "off" to be storing a 0. Just as in storing information on a disk, where it was easier to magnetize a region in either of two directions, it's a lot easier to make a switch that can be turned on or off reliably and quickly than one that can be set to any value from 0 to 9 reliably and quickly. This is particularly important when you're manufacturing millions of them on a silicon chip the size of your fingernail.
A main difference between disk and RAM is what steps are needed to access different areas of storage. In the case of the disk, the head has to be moved to the right track (an operation known as a seek), and then we have to wait for the platter to spin so that the region we want to access is under the head (called rotational delay). On the other hand, with RAM, the entire process is electronic; we can read or write any byte immediately as long as we know which byte we want. To specify a given byte, we have to supply a unique number called its memory address or just address for short.
What is an address good for? Let's see how my discussion with Susan on this topic started:
Susan: About memory addresses: are you saying that each little itty bitty tiny byte of RAM is a separate address? Well, this is a little hard to imagine.In case the notion of an address of a byte of memory on a piece of silicon is too abstract, it might help to think of an address as a set of directions as to how to find the byte being addressed, much like directions to someone's house. For example, "Go three streets down, then turn left. It's the second house on the right". With such directions, the house number wouldn't need to be written on the house. Similarly, the memory storage areas in RAM are addressed by position; you can think of the address as telling the hardware which street and house you want, by giving directions similar in concept to the preceding example. Therefore, it's not necessary to encode the addresses into the RAM explicitly.
Steve: Actually, each byte of RAM has a separate address, which doesn't change, and a value, which does.
Susan wanted a better picture of this somewhat abstract idea:
Susan: Where are the bytes on the RAM, and what do they look like?Since it has no moving parts, storing and retrieving data in RAM is much faster than waiting for the mechanical motion of a disk platter turning.12 As we've just seen, disk access times are measured in milliseconds, or thousandths of a second. However, RAM access times are measured in nanoseconds (abbreviated ns); nano means one billionth. In early 1997, a typical speed for RAM was 70 ns, which means that it is possible to read a given data item from RAM about 200,000 times as quickly as from a disk. In that case, why not use disks only for permanent storage, and read everything into RAM in the morning when we turn on the machine?
Steve: Each byte corresponds to a microscopic region of the RAM chip. As to what they look like, have you ever seen a printed circuit board such as the ones inside your computer? Imagine the lines on that circuit board reduced thousands of times in size to microscopic dimensions, and you'll have an idea of what a RAM chip looks like inside.
The reason is cost. In early 1997, the cost of 16 Megabytes of RAM was approximately $80. For that same amount of money, you could have bought over 1100 Megabytes of disk space!13 Therefore, we must reserve RAM for tasks where speed is all-important, such as running your word processing program and holding a letter while you're working on it. Also, since RAM is an electronic storage medium (rather than a magnetic one), it does not maintain its contents when the power is turned off. This means that if you had a power failure while working with data only in RAM, you would lose everything you had been doing.14 This is not merely a theoretical problem, by the way; if you don't remember to save what you're doing in your word processor once in a while, you might lose a whole day's work from a power outage of a few seconds.15 Before we get to how a program actually works, we need to develop a better picture of how RAM is used. As I've mentioned before, you can think of RAM as consisting of a large number of bytes, each of which has a unique identifier called an address. This address can be used to specify which byte we mean, so the program might specify that it wants to read the value in byte 148257, or change the value in byte 66666. Susan wanted to make sure she had the correct understanding of this topic:
Susan: Are the values changed in RAM depending on what program is loaded in it?This is all very well, but it doesn't answer the question of how the program actually uses or changes values in RAM, or performs arithmetic and other operations; that's the job of the CPU, which we will take up next.
Steve: Yes, and they also change while the program is executing. RAM is used to store both the program itself and the values it manipulates.
The CPU (Central Processing Unit) is the "active" component in the computer. Like RAM, it is physically composed of millions of microscopic transistors on a chip; however, the organization of these transistors in a CPU is much more complex than on a RAM chip, as the latter's functions are limited to the storage and retrieval of data. The CPU, on the other hand, is capable of performing dozens or hundreds of different fundamental operations called machine instructions, or just instructions for short. While each instruction performs a very simple function, the tremendous power of the computer lies in the fact that the CPU can perform (or execute) tens or hundreds of millions of these instructions per second.16 These instructions fall into a number of categories: instructions that perform arithmetic operations such as adding, subtracting, multiplying, and dividing; instructions that move information from one place to another in RAM; instructions that compare two quantities to help make a determination as to which instructions need to be executed next and instructions that implement that decision; and other, more specialized types of instructions.
Of course, adding two numbers together (for example) requires that the numbers be available for use. Possibly the most straightforward way of making them available is to store them in and retrieve them from RAM whenever they are needed, and indeed this is done sometimes. However, as fast as RAM is compared to disk drives (not to mention human beings), it's still pretty slow compared to modern CPUs. For example, the computer on which I started to write this book had a 66 Megahertz (abbreviated MHz) CPU, which can execute up to 66 million instructions per second (abbreviated MIPS),17 or one instruction approximately every 16 ns.18 To see why RAM is a bottleneck, let's calculate how long it would take to execute an instruction if all the data had to come from and go back to RAM. A typical instruction would have to read some data from RAM, and write its result back there; first, though, the instruction itself has to be loaded (or fetched) into the CPU before it can be executed. Let's suppose we have an instruction in RAM, reading one data item also in RAM, and writing the result back to RAM. Then the minimum timing to do such an instruction could be calculated as in Figure lowspeed.
Time Function
70 ns Read instruction from RAM
70 ns Read data from RAM
16 ns Execute instruction
70 ns Write result back to RAM
------
226 ns Total instruction execution time
To compute the effective MIPS of a CPU, we divide 1 second by the time it takes to execute one instruction. Given the assumptions in this example, the CPU could execute only about 4.5 million instructions per second, which is a far cry from the peak performance of 66 MIPS claimed by the manufacturer.19 If the manufacturer's claims have any relation to reality, there must be a better way.
In fact, there is. As a result of a lot of research and development, both in academia and in the semiconductor industry, it is possible to approach the rated performance of fast CPUs.20 Some of these techniques have been around as long as we've had computers; others have fairly recently "trickled down" from supercomputers to microcomputer CPUs. One of the most important of these techniques is the use of a number of different kinds of storage devices having different performance characteristics; the arrangement of these devices is called the memory hierarchy. Figure hierarchyfig illustrates the memory hierarchy on my home machine when I started writing this book in late 1994.
Susan and I had a short discussion of the layout of this figure:
Susan: OK, just one question on Figure hierarchyfig. If you are going to include the disk in this hierarchy, I don't know why you have placed it over to the side of RAM and not above it, since it is slower and you appear to be presenting this figure in ascending order of speed from the top of the figure downward. Did you do this because it is external rather than internal memory and it doesn't "deserve" to be in the same lineage as the others?
Steve: Yes; it's not the same as "real" memory, so I wanted to distinguish it.
Before we get to the diagram, I should explain that a cache is a small amount of fast memory where frequently used data are stored temporarily. According to this definition, RAM functions more or less as a cache for the disk; after all, we have to copy data from a slow disk into fast RAM before we can use it for anything. However, while this is a valid analogy, I should point out that the situations aren't quite parallel. Our programs usually read data from disk into RAM explicitly; that is, we're aware of whether it's on the disk or in RAM, and we have to issue commands to transfer it from one place to the other. On the other hand, caches are "automatic" in their functioning. We don't have to worry about them, and our programs work in exactly the same way with them as without them, except faster. In any event, the basic idea is the same: to use a faster type of memory to speed up repetitive access to data usually stored on a slower storage device.
We've already seen that the disk is necessary to store data and programs when the machine is turned off, while RAM is needed for its higher speed in accessing data and programs we're currently using.21 But why do we need the external cache?
Actually, we've been around this track before, when we questioned why everything isn't loaded into RAM rather than being read from the disk as needed; we're trading speed for cost. To have a cost-effective computer with good performance requires the designer to choose the correct amount of each storage medium.
+-------------------+ +--------------------+ | | | | | Disk +---+ RAM | | Size: 850 MB | | Size: 20 MB | | Accesses: 100/sec.| +-+ Accesses: 14 M/sec.+--+ +-------------------+ | +--------+-----------+ | | | | | +--------+------------+ | | | | | | | External cache | | | | Size: 64 KB | | | | Accesses: 30 M/sec. | | | +------+--------------+ | | | | +---------------------+--------+----------------+---+ | | | | | | The | +------+------+ | | | CPU +-------+-+-+ | | | | chip | | +--------+---------+-+ | | | Execution | | | | | | unit +--+ Internal cache | | | | | | Size: 8 KB | | | +---+-------+ | Accesses: 66 M/sec.| | | | +--------------------+ | | +-------+---------------------+ | | | +--------+-----------+ | | | | | | ax | eax | | | | +--------+-----------+ | | | | +--------+-----------+ | | | | | | bx | ebx | | | | +--------+-----------+ | | | | +--------+-----------+ | | | | | | cx | ecx | | | | +--------+-----------+ | | | | +--------+-----------+ | | | | | | dx | edx | | | | +--------+-----------+ | | | | +--------+-----------+ | | | | | | si | esi | | | | +--------+-----------+ | | | | +--------+-----------+ | | | | | | di | edi | | | | +--------+-----------+ | | | | +--------+-----------+ | | | | | | bp | ebp | | | | +--------+-----------+ | | | | Registers | | | | Size: 28 bytes | | | | Accesses: 133 M/sec. | | | +-----------------------------+ | +---------------------------------------------------+
So just as with the disk vs. RAM trade-off before, the reason that we use the external cache is to improve performance. While RAM can be accessed about 14 million times per second, the external cache is made from a faster type of memory chips, which can be accessed about 30 million times per second. While not as extreme as the speed differential between disk and RAM, this difference is still significant. However, we can't afford to use external cache exclusively instead of RAM, because it would be too expensive to do so. In 1997, the cost of 1 MB of external cache was in the neighborhood of $180. For that same amount of money, you could have bought over 16 Megabytes of RAM. Therefore, we must reserve external cache for tasks where speed is all-important, such as supplying frequently used data or programs to the CPU.22 The same analysis applies to the trade-off between the external cache and the internal cache. The internal cache's characteristics are similar to those of the the external cache, but to a greater degree; it's even smaller and faster, allowing access at the rated speed of the CPU. Both characteristics have to do with its privileged position on the same chip as the CPU; this reduces the delays in communication between the internal cache and the CPU but means that chip area devoted to the cache has to compete with area for the CPU, as long as the total chip size is held constant.
Unfortunately, we can't just increase the size of the chip to accommodate more internal cache because of the expense of doing so. Larger chips are more difficult to make, which reduces their yield, or the percentage of good chips. In addition, fewer of them fit on one wafer, which is the unit of manufacturing. Both of these attributes make larger chips more expensive to make.
To oversimplify a bit, here's how caching reduces the effects of slow RAM. Whenever a data item is requested by the CPU, there are three possibilities:
Another way to improve performance that has been employed for many years is to create a small number of private storage areas, called registers, that are on the same chip as the CPU itself.25 Programs use these registers to hold data items that are actively in use; data in registers can be accessed within the time allocated to instruction execution (16 ns in our example), rather than the much longer times needed to access data in RAM. This means that the time needed to access data in registers is predictable, unlike data that may have been displaced from the internal cache by more recent arrivals and thus must be reloaded from the external cache or even from RAM. Most CPUs have some dedicated registers, which aren't available to application programmers (that's us), but are reserved for the operating system (e.g., DOS, Unix, OS/2) or have special functions dictated by the hardware design; however, we will be concerned primarily with the general registers, which are available for our use.26 The general registers are used to hold working copies of data items called variables, which otherwise reside in RAM during the execution of the program. These variables represent specific items of data that we wish to keep track of in our programs, such as weights and numbers of items.
The notion of using registers to hold temporary copies of variables wasn't crystal clear to Susan. Here's our discussion on that topic:
Susan: Here we go, getting lost. When you said "The general registers are used to hold working copies of data items called variables, which reside in RAM", are you saying RAM stores info when not in use?You can put something in a variable, and it will stay there until you store something else there; you can also look at it to find out what's in it. As you might expect, several types of variables are used to hold different kinds of data; the first ones we will look at are variables representing whole numbers (the so-called integer variables), which are a subset of the category called numeric variables. As this suggests, there are also variables that represent numbers that can have fractional parts. We'll look at these so-called floating-point variables briefly in a later chapter.
Steve: During execution of a program, when data aren't in the general registers, they are generally stored in RAM.
Susan: See, this is confusing to me, because I didn't think RAM stores anything when turned off.
Steve: You're correct; RAM doesn't retain information when the machine is turned off. However, it is used to keep the "real" copies of data that we want to process but won't fit in the registers.27
Different types of variables require different amounts of RAM to store them, depending on the amount of data they contain; a very common type of numeric variable, known as a short, requires 16 bits (that is, 2 bytes) of RAM to hold any of 65536 different values, from -32768 to 32767, including 0. As we will see shortly, these odd-looking numbers are the result of using the binary system. By no coincidence at all, the early Intel CPUs such as the 8086 had general registers that contained 16 bits each; these registers were named ax, bx, cx, dx, si, di, and bp. Why does it matter how many bits each register holds? Because the number (and size) of instructions it takes to process a variable is much less if the variable fits in a register; therefore, most programming languages, C++ included, relate the size of a variable to the size of the registers available to hold it. A short is exactly the right size to fit into a 16-bit register and therefore can be processed efficiently by the early Intel machines, whereas longer variables had to be handled in pieces, causing a great decline in efficiency of the program. Progress marches on: more recent Intel CPUs, starting with the 80386, have 32-bit general registers; these registers are called eax, ebx, ecx, edx, esi, edi, and ebp. You may have noticed that these names are simply the names of the old 16-bit registers with an e tacked onto the front. The reason for the name change is that when Intel increased the size of the registers to 32 bits with the advent of the 80386, it didn't want to change the behavior of previously existing programs that (of course) used the old names for the 16-bit registers. So the old names, as illustrated in Figure hierarchyfig, now refer to the bottom halves of the "real" (that is, 32-bit) registers, as illustrated in Figure hierarchyfig; instructions using these old names behave exactly as though they were accessing the 16-bit registers on earlier machines. To refer to the 32-bit registers, you use the new names eax, ebx, and so on, for "extended" ax, "extended" bx, and so forth. What does it mean to say that instructions using the 16-bit register names "behave exactly as though they were accessing the 16-bit registers on earlier machines"? Before I can explain this, you'll have to understand the binary number system, on which all modern computers are based. To make this number system more intelligible, I have written the following little fable.
Once upon a time, the Acme company had a factory that made golf carts. One day, Bob, the president of Acme, decided to add an odometer to the carts, so that the purchaser of the cart could estimate when to recharge the battery. To save money, Bob decided to buy the little numbered wheels for the odometers and have his employees put the odometers together. The minimum order was a thousand odometer wheels, which was more than he needed for his initial run of 50 odometers. When he got the wheels, however, he noticed that they were defective: Instead of the numbers 0-9, each wheel had only two numbers, 0 and 1. Of course, he was quite irritated by this error, and attempted to contact the company from which he had purchased the wheels, but it had closed down for a month for summer vacation. What was he to do until it reopened?
While he was fretting about this problem, the employee who had been assigned to the task of putting the odometers together from the wheels came up with a possible solution. This employee, Jim, came into Bob's office and said, "Bob, I have an idea. Since we have lots of orders for these odometer-equipped carts, maybe we can make an odometer with these funny wheels and tell the customers how to read the numbers on the odometer."
Bob was taken aback by this idea. "What do you mean, Jim? How can anyone read those screwy odometers?"
Jim had given this some thought. "Let's take a look at what one of these odometers, say with five wheels, can display. Obviously, it would start out reading 00000, just like a normal odometer. Then when one mile has elapsed, the rightmost wheel turns to 1, so the whole display is 00001; again, this is no different from a normal odometer."
"Now we come to the tricky part. The rightmost wheel goes back to 0, not having any more numbers to display, and pushes the `tens' wheel to 1; the whole number now reads 00010. Obviously, one more mile makes it 00011, which gives us the situation shown in the following diagram:
Normal odometer Funny odometer00000 00000
00001 00001
00002 00010
00003 00011
Jim continued, "What's next? This time, the rightmost wheel turns over again to 0, triggering the second wheel to its next position. However, this time, the second wheel is already at its highest value, 1; therefore, it also turns over to 0 and increments the third wheel. It's not hard to follow this for a few more miles, as illustrated in Figure nextfew.
Normal odometer Funny odometer00004 00100
00005 00101
00006 00110
00007 00111
Bob said, "I get it. It's almost as though we were counting normally, except that you skip all the numbers that have anything but 0s or 1s in them."
"That's right, Bob. So I suppose we could make up a list of the `real' numbers and give it to the customers to use until we can replace these odometers with normal ones. Perhaps they'll be willing to work with us on this problem."
"Okay, Jim, if you think they'll buy it. Let's get a few of the customers we know the best and ask them if they'll try it; we won't charge them for the odometers until we have the real ones, but maybe they'll stick with us until then. Perhaps any odometer would be better than no odometer at all."
Jim went to work, making some odometers out of the defective wheels; however, he soon figured out that he had to use more than five wheels, because that allowed only numbers from 0 to 31. How did he know this?
Each wheel has two numbers, 0 and 1. So with one wheel, we have a total of two combinations. Two wheels can have either a 0 or a 1 for the first number, and the same for the second number, for a total of four combinations. With three wheels, the same analysis holds: 2 numbers for the first wheel * 2 for the second wheel * 2 for the third wheel = 8 possibilities in all; actually, they are the same 8 possibilities we saw in Figures firstfew and nextfew.
A pattern is beginning to develop: for each added wheel, we get twice as many possible combinations. To see how this continues, take a look at Figure howmany, which shows the count of combinations vs. number of wheels for all wheel counts up to 16 (i.e., 16-bit quantities).
Jim decided that 14 wheels would do the job, since the lifespan of the golf cart probably wouldn't exceed 16,383 miles, and so he made up the odometers. The selected customers turned out to be agreeable and soon found that having even a weird odometer was better than none, especially since they didn't have to pay for it. However, one customer did have a complaint: The numbers on the wheels didn't seem to make sense when translated with the chart supplied by Acme. The customer estimated that he had driven the cart about 9 miles, but the odometer displayed the following number,
11111111110111
which, according to his translation chart, was 16375 miles. What could have gone wrong?
Number of wheels Number of combinations28 1 22 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024
11 2048
12 4096
13 8192
14 16384
15 32768
16 65536
Jim decided to have the cart brought in for a checkup, and what he discovered was that the odometer cable had been hooked up backwards. That is, instead of turning the wheels forward, they were going backwards. That was part of the solution, but why was the value 16375? Just like a car odometer, in which 99999 (or 999999, if you have a 6-wheel odometer) is followed by 0, going backwards from 0 reverses that progression. Similarly, the number 11111111111111 on the funny odometers would be followed by 00000000000000, since the "carry" off the leftmost digit is lost. Therefore, if you start out at 0 and go backward 1 mile, you'll get
11111111111111
The next mile will turn the last digit back to 0, producing
11111111111110
What happens next? The last wheel turns back to 1, and triggers the second wheel to switch as well:
11111111111101
The next few "backward" numbers look like this:
11111111111100
11111111111011
11111111111010
11111111111001
11111111111000
11111111110111
and so on. If you look at the right-hand end of these numbers, you'll see that the progression is just the opposite of the "forward" numbers.
As for the customer's actual mileage, the last one of these is the number the customer saw on his backward odometer. Apparently, he was right about the distance driven, since this is the ninth "backward" number. So Jim fixed the backward odometer cable and reset the value to the correct number, 00000000001001, or 9 miles.
Eventually, Acme got the right odometer wheels with 0-9 on them, replaced the peculiar ones, and everyone lived happily ever after.
THE END
Of course, the wheels that made up the funny odometers contain only two digits, 0 and 1, so the odometers use the binary system for counting. Now it should be obvious why we will see numbers like 65536 and 32768 in our discussions of the number of possible different values that a variable can hold: variables are stored in RAM as collections of bytes, each of which contains 8 bits. As the list of combinations indicates, 8 bits (1 byte) provide 256 different combinations, while 16 bits (2 bytes) can represent 65536 different possible values.
But what about the "backward" numbers with a lot of 1s on the left? As the fable suggests, they correspond to "negative" numbers. That is, if moving 2 miles forward from 0 registers as 00000000000010, and moving 2 miles backward from 0 registers as 11111111111110, then the latter number is in some sense equivalent to -2 miles. This in fact is the way that negative integers are stored in the computer; integer variables that can store either positive or negative values are called signed variables. If we don't specify whether we want to be able to store either positive or negative values in a given variable, the C++ language assumes that we want that ability, and provides it for us by default.
However, adding the ability to represent negative numbers has a drawback: namely, that you can't represent as many positive numbers. This should be fairly obvious, since if we interpret some of the possible patterns as negative, they can't also be used for positive values. Sometimes, of course, we don't have to worry about negative numbers, such as counting how many employees our company has; in such cases, we can specify that we want to use unsigned variables, which will always be interpreted as positive (or 0) values. An example is an unsigned short variable, which uses 16 bits (that is, 2 bytes) to hold any number from 0 to 65535, which totals 65536 different values. This capacity can be calculated as follows: since each byte is 8 bits, 2 bytes contain a total of 16 bits, and 2^16 is 65536.
It's important to understand that the difference between a short (that is, a signed short) and an unsigned short is exactly which 65536 values each can hold. An unsigned short can hold any whole number from 0 to 65535, whereas a short can hold any value from -32768 to +32767.
I hope this is clear to you, but in case it isn't, let's see how Susan and I worked over this point:
Susan: I really don't think I understand what ashortis besides being 2 bytes of RAM, and I don't really know whatsignedandunsignedmean.
Steve: A
shortis indeed 2 bytes (that is, 16 bits) of RAM. This means that it can hold any of 2^16 (65536) different values. This is a very nice range of values for holding the number of pounds that a pumpkin weighs (for example). You'll see some more uses for this type of variable later.The difference between a (
signed)shortand anunsignedshortis exactly which 65536 values each can hold. Anunsignedshortcan hold any whole number from 0 to 65535, whereas a (signed)shortcan hold any value from -32768 to +32767. The difference between these is solely in the interpretation that we (and the compiler) give to the values. In other words, it's not possible to tell whether a given 2 bytes of RAM represent ashortor anunsignedshortby looking at the contents of those bytes; you have to know how the variable was defined in the program.
Susan: Ok, let's start over. A
shortis 2 bytes of RAM. Ashortis a variable. Ashortis a numeric variable. It can besigned(why is that a default?), meaning its value can be -32768 to +32767, orunsigned, meaning its value can be 0-65535. How's that?
Steve: That's fine. Since you've asked, the reason
signedis the default is because that's the way it was in C, and changing it in C++ would "break" C programs that depended on this default. Bjarne Stroustrup, the inventor of C++, has a rule that C++ must be as close to C as possible but no closer. In this case, there's no real reason to change the default, so it wasn't changed.
Susan: Oh, why is it that every time you say something is fairly obvious, my mind just shuts down? When you say "if we interpret some of the possible patterns as negative, they can't also be used for positive values." Huh? Then if that is the case would not the reverse also be true? I can see how this explains the values of the signed and unsigned short, but really I don't think I have grasped this concept.
Steve: What I was trying to explain is that you have to choose one of the following two possibilities:29
- (
signed)shortrange: -32768 to +32767unsigned shortrange: 0 to 65535In other words, you have to decide whether you want a given variable to represent:
- Any of 32768 negative numbers, 0, or 32767 positive numbers, or
- Any of 65536 nonnegative numbers from 0 to 65535
If you want a variable with a range like that in selection 1, use a (
signed)short; if you prefer the range in selection 2, use anunsigned short. For example, for the number of lines in a text file, you could use anunsigned short, since the maximum number of lines could be limited to less than 65,000 lines and couldn't ever be negative. On the other hand, to represent the number of copies of a book that have been sold in the last month, including the possibility of returns exceeding sales, asignedshortwould be better, since the value could be either positive or negative.
Susan: In other words, if you are going to be using variables that might have a negative value then use a
signedshort, and if you want strictly "positive" numbers then use anunsignedshort. Right?
Steve: Exactly!
Susan: Well, then, how do you write a
shortto indicate that it issignedorunsigned?
Steve: When you define it, you have to specify that it is
unsignedif you want it to beunsigned; the default issigned. In other words, if we define a variablexasshort x;, it will besigned, whereas if we want a variable calledxthat is anunsigned short,we have to sayunsigned short x;.
Susan: So does it make any difference if your variable is going to overlap the
signedandunsigned shortranges? For example, if you are using numbers from 10,000 to 30,000, would it matter whichshortyou used? It falls under the definition of both.
Steve: You can use whichever you wish in that case.
You may have noticed that it's tedious and error prone to represent numbers in binary; a long string of 0s and 1s is hard to remember or to copy. For this reason, the pure binary system is hardly ever used to specify numbers in computing. However, we have already seen that binary is much more "natural" for computers than the more familiar decimal system. Is there a number system that we humans can use a little more easily than binary, while retaining the advantages of binary for describing internal events in the computer?
As it happens, there is. It's called hexadecimal, which means "base 16". As a rule, the term hexadecimal is abbreviated to hex. Since there are 16 possible combinations of 4 bits (2*2*2*2), hexadecimal notation allows 4 bits of a binary number to be represented by one hex digit. Unfortunately, however, there are only 10 "normal" digits, 0-9.30 To represent a number in any base, you need as many different digit values as the base, so that any number less than the base can be represented by one digit. For example, in base 2, you need only two digits, 0 and 1. In base 8 (octal), you need eight digits, 0-7.31 So far, so good. But what about base 16? To use this base, we need 16 digits. Since only 10 numeric digits are available, hex notation needs a source for the other six digits. Because letters of the alphabet are available and familiar, the first six letters, a-f, were adopted for this service.32 Although the notion of a base-16 numbering system doesn't seem strange to people who are familiar with it, it can really throw someone who learned normal decimal arithmetic solely by rote, without understanding the concepts on which it is based. This topic of hexadecimal notation occupied Susan and me for quite awhile; here's some of the discussion we had about it:
Susan: I don't get this at all! What is the deal with the letters in the hex system? I guess it would be okay if 16 wasn't represented by 10!Now that we've seen how each hex digit corresponds exactly to a group of four binary digits, here's an exercise you can use to improve your understanding of this topic: Invent a random string of four binary digits and see where it is in figure binhex. I guarantee it'll be there somewhere! Then look at the "hex" column and see what "digit" it corresponds to. There's nothing really mysterious about hex; since we have run out of digits after 9, we have to use letters to represent the numbers `ten', `eleven', `twelve', `thirteen', `fourteen', and `fifteen'.
Steve: Well, there are only 10 "normal" digits, 0-9. To represent a number in any base, you need as many "digits" as the base, so that any number less than the base can be represented by one "digit". This is no problem with a base less than ten, such as octal, but what about base 16? To use this base we need 16 digits, 0-9 and a-f. One way to remember this is to imagine that the "hex" in "hexadecimal" stands for the six letters a through f and the "decimal" stands for the 10 digits 0-9.
Susan: OK, so a hex digit represents 16 bits? So then is hex equal to 2 bytes? According to the preceding a hex digit is 4 bits.
Steve: Yes, a hex digit represents 4 bits. Let's try a new approach. First, let me define a new term, a hexit. That's short for "hex digit", just like "bit" is short for "binary digit".
- How many one-digit decimal numbers exist?
- How many two-digit decimal numbers exist?
- How many three-digit decimal numbers exist?
- How many four-digit decimal numbers exist?
- How many one-bit binary numbers exist?
- How many two-bit binary numbers exist?
- How many three-bit binary numbers exist?
- How many four-bit binary numbers exist?
- How many one-hexit hexadecimal numbers exist?
- How many two-hexit hexadecimal numbers exist?
- How many three-hexit hexadecimal numbers exist?
- How many four-hexit hexadecimal numbers exist?
The answers are:
- 10
- 100
- 1000
- 10000
- 2
- 4
- 8
- 16
- 16
- 256
- 4096
- 65536
What do all these answers have in common? Let's look at the answers a little differently, in powers of 10, 2, and 16, respectively:
- 10 = 10^1
- 100 = 10^2
- 1000 = 10^3
- 10000 = 10^4
- 2 = 2^1
- 4 = 2^2
- 8 = 2^3
- 16 = 2^4
- 16 = 16^1
- 256 = 16^2
- 4096 = 16^3
- 65536 = 16^4
That is, a number that has one digit can represent "base" different values, where "base" is two, ten, or sixteen (in our examples). Every time we increase the size of the number by one more digit, we can represent "base" times as many possible different values, or in other words, we multiply the range of values that the number can represent by the base. Thus, a two-digit number can represent any of "base*base" values, a three-digit number can represent any of "base*base*base" values, and so on. That's the way positional number systems such as decimal, binary, and hex work. If you need a bigger number, you just add more digits.
Okay, so what does this have to do with hex? If you look at the above table, you'll see that 2^4 (16) is equal to 16^1. That means that 4 bits are exactly equivalent to one hexit in their ability to represent different numbers: exactly 16 possible numbers can be represented by four bits, and exactly 16 possible numbers can be represented by one hexit.
This means that you can write one hexit wherever you would otherwise have to use four bits, as illustrated in Figure binhex.
Binary to hex conversion table (Figure binhex)
4-bit value 1-hexit value
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 a
1011 b
1100 c
1101 d
1110 e
1111 f
So an 8-bit number, such as:
0101 1011
can be translated directly into a hex value, like this:
5 b
For this reason, binary is almost never used. Instead, we use hex as a shortcut to eliminate the necessity of reading, writing, and remembering long strings of bits.
Susan: A hex digit or hexit is like a four-wheel odometer in binary. Since each wheel is capable of only one of two values, being either (1) or (0), then the total number of possible values is 16. Thus your 2*2*2*2 = 16. I think I've got this down.
Steve: You certainly do!
Susan: If it has 4 bits and you have 2 of them then won't there be eight "wheels" and so forth? So 2 hex would hold XXXXXXXX places and 3 hex would hold XXXXXXXXXXXX places.
Steve: Correct. A one-hexit number is analogous to a one-digit decimal number. A one-hexit number contains 4 bits and therefore can represent any of 16 values. A two-hexit number contains 8 bits and therefore can represent any of 256 values.
Now, here's a table showing the correspondence between some decimal, hex, and binary numbers, with the values of each digit position in each number base indicated, and the calculation of the total of all of the bit values in the binary representation, as shown in Figure diffrep.
Decimal Hexadecimal Binary Sum of binaryPlace Values Place Values Place Values digit values
10 1 16 1 16 8 4 2 1
0 0 0 0 0 0 0 0 = 0 + 0 + 0 + 0 + 0
1 0 1 0 0 0 0 1 = 0 + 0 + 0 + 0 + 1
2 0 2 0 0 0 1 0 = 0 + 0 + 0 + 2 + 0
3 0 3 0 0 0 1 1 = 0 + 0 + 0 + 2 + 1
4 0 4 0 0 1 0 0 = 0 + 0 + 4 + 0 + 0
5 0 5 0 0 1 0 1 = 0 + 0 + 4 + 0 + 1
6 0 6 0 0 1 1 0 = 0 + 0 + 4 + 2 + 0
7 0 7 0 0 1 1 1 = 0 + 0 + 4 + 2 + 1
8 0 8 0 1 0 0 0 = 0 + 8 + 0 + 0 + 0
9 0 9 0 1 0 0 1 = 0 + 8 + 0 + 0 + 1
1 0 0 a 0 1 0 1 0 = 0 + 8 + 0 + 2 + 0
1 1 0 b 0 1 0 1 1 = 0 + 8 + 0 + 2 + 1
1 2 0 c 0 1 1 0 0 = 0 + 8 + 4 + 0 + 0
1 3 0 d 0 1 1 0 1 = 0 + 8 + 4 + 0 + 1
1 4 0 e 0 1 1 1 0 = 0 + 8 + 4 + 2 + 0
1 5 0 f 0 1 1 1 1 = 0 + 8 + 4 + 2 + 1
1 6 1 0 1 0 0 0 0 = 16 + 0 + 0 + 0 + 0
1 7 1 1 1 0 0 0 1 = 16 + 0 + 0 + 0 + 1
1 8 1 2 1 0 0 1 0 = 16 + 0 + 0 + 2 + 0
1 9 1 3 1 0 0 1 1 = 16 + 0 + 0 + 2 + 1
Another reason to use hex rather than decimal is that byte values expressed as hex digits can be combined directly to produce larger values, which is not true with decimal digits. In case this isn't obvious, let's go over it in more detail. Since each hex digit (0-f) represents exactly 4 bits, two of them (00-ff) represent 8 bits, or one byte. Similarly, 4 hex digits (0000-ffff) represent 16 bits, or a short value; the first two digits represent the first byte of the 2-byte value, and the last two digits, the second byte. This can be extended to any number of bytes. On the other hand, representing 4 bits requires two decimal digits, as the values range from 00-15, whereas it takes three digits (000-255) to represent one byte. A 2-byte value requires five decimal digits, since the value can be from 00000 to 65535. As you can see, there's no simple relationship between the decimal digits representing each byte and the decimal representation of a 2-byte value.
Susan had some more thoughts on the hexadecimal number system. Let's listen in:
Susan: I think you need to spend a little more time reviewing the hex system, like an entire chapter.<G> Well, I am getting the impression that we are going to be working with hex, so I am trying to concentrate my understanding on that instead of binary. I think this all moves a little too fast for me. I don't know what your other reviewers are saying but I just feel like I get a definition of a abstract concept, and the next thing I know I am supposed to be doing something with it, like make it work. Ha! I personally need to digest new concepts, I really need to think them over a bit, to take them in and absorb them. I just can't start working with it right away.As usual, I've complied with her request; the results are immediately ahead.
Here are some exercises that you can use to check your understanding of the binary and hexadecimal number systems.33 I've limited the examples to addition and subtraction, as that is all that you're ever likely to have to do in these number systems. These operations are exactly like their equivalents in the decimal system, except that as we have already seen, the hexadecimal system has six extra digits after 9: a, b, c, d, e, and f. We have to take these into account in our calculations: for example, adding 9 and 5, rather than producing 14, produces e.
1. Using the hexadecimal system, answer these problems:
a. 1a + 2e = ?
b. 12 + 18 = ?
c. 50 - 12 = ?
2. In the binary system, answer these problems:
a. 101 + 110 = ?
b. 111 + 1001 = ?
c. 1010 - 11 = ?
Consider the two types of numeric variables we've encountered so far, short and unsigned short. Let's suppose that x is a short, and y is an unsigned short, both of them currently holding the value 32767, or 7fff in hex.
3. What is the result of adding 1 to y, in both decimal and hex?
4. What is the result of adding 1 to x, in both decimal and hex?
Answers to exercises can be found at the end of the chapter.
Before we took this detour into the binary and hexadecimal number systems, I promised to explain what it means to say that the instructions using the 16-bit register names "behave exactly as though they were accessing the 16-bit registers on earlier machines". After a bit more preparation, we'll be ready for that explanation.
First, let's take a look at some characteristics of the human-readable version of machine instructions: assembly language instructions. The assembly language instructions we will look at have a fairly simple format.34 The name of the operation is given first, followed by one or more spaces. The next element is the "destination", which is the register or RAM location that will be affected by the instruction's execution. The last element in an instruction is the "source", which represents another register, a RAM location, or a constant value to be used in the calculation. The source and destination are separated by a comma.35 Here's an example of a simple assembly language instruction:
add ax,1
In this instruction, add is the operation, ax is the destination, and the constant value 1 is the source. Thus, add ax,1 means to add 1 to the contents of ax, replacing the old contents of ax with the result.
Let's see what Susan has to say about the makeup of an assembly language instruction:
Susan: So the destination can be a register, cache, or RAM?Now we're finally ready to see what the statement about using the 16-bit register names on a 32-bit machine means. Suppose we have the register contents shown in Figure beforeaddax.1 (indicated in hexadecimal).
Steve: Yes, that's right. However, I should make it clear that the cache is transparent to the programmer. That is, you don't say "write to the cache" or "read from the cache"; you just use the RAM addresses and the hardware takes care of using the cache as appropriate to speed up access to frequently used locations. On the other hand, you do have to address registers explicitly when writing an assembly language program.
32 and 16 bit registers, before
32-bit 32-bit 16-bit 16-bitadd ax,1(Figure beforeaddax.1)register contents register contents
eax 1235ffff ax ffff
If we were to add 1 to register ax, by executing the instruction add ax,1, the result would be as shown in Figure afteraddax.1.
32 and 16 bit registers, after
32-bit 32-bit 16-bit 16-bitadd ax,1(Figure afteraddax.1)register contents register contents
eax 12350000 ax 0000
In case this makes no sense, consider what happens when you add 1 to 9999 on a four digit counter such as an odometer. It "turns over" to 0000, doesn't it? The same applies here: ffff is the largest number that can be represented as four hex digits, so if you add 1 to a register that has only four (hex) digits of storage available, the result is 0000.
As you might imagine, Susan was quite intrigued with the above detail; here is her reaction.
Susan: I have a understanding retention half-life of about 30 nanoseconds, but while I was reading this I was understanding it except I am boggled as to how adding 1 to ffff makes 0000, see, I am still not clear on Hex. Question: When you show the contents of a 32-bit register as being 12350000, then is the 1235 the upper half and the 0000 the lower half? Is that what you are saying?As this illustrates, instructions that refer to
Steve: That's right!
ax have no effect whatever on the upper part of eax; they behave exactly as though the upper part of eax did not exist. However, if we were to execute the instruction add eax,1 instead of add ax,1, the result would look like Figure afteraddeax.1.
32 and 16 bit registers, after
32-bit 32-bit 16-bit 16-bitadd eax,1(Figure afteraddeax.1)register contents register contents
eax 12360000 ax 0000
In this case, eax is treated as a whole. Similar results apply to the other 32-bit registers and their 16-bit counterparts.
Unfortunately, it isn't possible to use only registers and avoid references to RAM entirely, if only because we'll run out of registers sooner or later. This is a good time to look back at the diagram of the "memory hierarchy" (figure hierarchyfig) and examine the relative speed and size of each different kind of memory.
The "size" attribute of the disk and RAM are specified in Megabytes, whereas the size of an external cache is generally in the range from 64 Kilobytes to 1 Megabyte. As I mentioned before, the internal cache is considerably smaller, usually in the 8 to 16 Kilobyte range. The registers, however, provide a total of 28 bytes of storage; this should make clear that they are the scarcest memory resource. To try to clarify why the registers are so important to the performance of programs, I've listed the "speed" attribute in number of accesses per second, rather than in milliseconds, nanoseconds, and so forth. In the case of the disk, this is about 100 accesses per second. RAM can be accessed about 14 million times per second. The clear winners, though, are the internal cache and the registers, which can be accessed 66 million times per second and 133 million times per second, respectively.
In a way, the latter figure (133 million accesses per second for registers) overstates the advantages of registers relative to the cache. You see, any given register can be accessed only 66 million times per second; however, many instructions refer to two registers and still execute in one CPU cycle. Therefore, the maximum number of references per second is more than the number of instructions per second.
However, this leads to another question: Why not have instructions that can refer to more than one memory address (known as memory-to-memory instructions) and still execute in one CPU cycle? In that case, we wouldn't have to worry about registers; since there's (relatively) a lot of cache and very few registers, it would seem to make more sense to eliminate the middleman and simply refer to data in the cache.36 Of course, there is a good reason for the provision of both registers and cache. The main drawback of registers is that there are so few of them; on the other hand, one of their main advantages is also that there are so few of them. Why is this?
The main reason to use registers is that they make instructions shorter: since there are only a few registers, we don't have to use up a lot of bits specifying which register(s) to use. That is, with eight registers, we only need 3 bits to specify which register we need. In fact, there are standardized 3-bit codes that might be thought of as "register addresses", which are used to specify each register when it is used to hold a variable. Figure registermapfig is the table of these register codes.37
Register 16-bit 32-bitaddress register register
000 ax eax
001 cx ecx
010 dx edx
011 bx ebx
100 sp esp
101 bp ebp
110 si esi
111 di edi
By contrast, with a "memory-to-memory" architecture, each instruction would need at least 2 bytes for the source address, and 2 bytes for the destination address.38 Adding 1 byte to specify what the instruction is going to do, this would make the minimum instruction size 5 bytes, whereas some instructions that use only registers can be as short as 1 byte. This makes a big difference in performance because the caches are quite limited in size; big programs don't fit in the caches, and therefore require a large number of RAM accesses. As a result, they execute much more slowly than small programs.
This explains why we want our programs to be smaller. However, it may not be obvious why using registers reduces the size of instructions, so here's an explanation.
Most of the data in use by a program are stored in RAM. When using a 32-bit CPU, it is theoretically possible to have over 4 billion bytes of memory (2^32 is the exact number). Therefore, that many distinct addresses for a given byte of data are possible; to specify any of these requires 32 bits. Since there are only a few registers, specifying which one you want to use takes only a few bits; therefore, programs use register addresses instead of memory addresses wherever possible, to reduce the number of bits in each instruction required to specify addresses.
I hope this is clear, but it might not be. It certainly wasn't to Susan. Here's the conversation we had on this topic:
Susan: I see that you are trying to make a point about why registers are more efficient in terms of making instructions shorter, but I just am not picturing exactly how they do this. How do you go from "make the instructions much shorter" to "we don't have to use up a lot of bits specifying which registers to use"?After that comedy routine, let's go back to Susan's reaction to something I said earlier about registers and variables:
Steve: Let's suppose that we want to move data from one place to another in memory. In that case, we'll have to specify two addresses: the "from" address and the "to" address. One way to do this is to store the addresses in the machine language instruction. Since each address is at least 16 bits, an instruction that contains two addresses needs to occupy at least 32 bits just for the addresses, as well as some more bits to specify exactly what instruction we want to perform. Of course, if we're using 32-bit addresses, then a "two-address" instruction would require 64 bits just for the two addresses, in addition to whatever bits were needed to specify the type of instruction.
Susan: OK. . . think I got this. . .
Steve: On the other hand, if we use registers to hold the addresses of the data, we need only enough bits to specify each of two registers. Since there aren't that many registers, we don't need as many bits to specify which ones we're referring to. Even on a machine that has 32 general registers, we'd need only 10 bits to specify two registers; on the Intel machines, with their shortage of registers, even fewer bits are needed to specify which register we're referring to.
Susan: Are you talking about the bits that are needed to define the instruction?
Steve: Yes.
Susan: How would you know how many bits are needed to specify the two registers?
Steve: If you have 32 different possibilities to select from, you need 5 bits to specify one of them, because 32 is 2 to the fifth power. If we have 32 registers, and any of them can be selected, that takes 5 bits to select any one of them. If we have to select two registers on a CPU with 32 registers, we need 10 bits to specify both registers.
Susan: So what does that have to do with it? All we are talking about is the instruction that indicates "select register" right? So that instruction should be the same and contain the same number of bits whether you have 1 or 32 registers.
Steve: There is no "select register" instruction. Every instruction has to specify whatever register or registers it uses. It takes 5 bits to select 1 of 32 items and only 3 bits to select 1 of 8 items; therefore, a CPU design that has 32 registers needs longer instructions than one that has only 8 registers.
Susan: I don't see why the number of registers should have an effect on the number of bits one instruction should have.
Steve: If you have two possibilities, how many bits does it take to select one of them? 1 bit. If you have four possibilities, how many bits does it take to select one of them? 2 bits. Eight possibilities require 3 bits; 16 possibilities require 4 bits; and finally 32 possibilities require 5 bits.
Susan: Some machines have 32 registers?
Steve: Yes. The PowerPC, for example. Some machines have even more registers than that.
Susan: If the instructions to specify a register are the same, then why would they differ just because one machine has more than another?
Steve: They aren't the same from one machine to another. Although every CPU that I'm familiar with has registers, each type of machine has its own way of executing instructions, including how you specify the registers.
Susan: OK, and in doing so it is selecting a register, right? An instruction should contain the same number of bits no matter how many registers it has to call on.
Steve: Let's take the example of an
addinstruction, which as its name implies, adds two numbers. The name of the instruction is the same length, no matter how many registers there are; that's true. However, the actual representation of the instruction in machine language has to have room for enough bits to specify which register(s) are being used in the instruction.
Susan: They are statements right? So why should they be bigger or smaller if there are more or fewer registers?
Steve: They are actually machine instructions, not C++ statements. The computer doesn't know how to execute C++ statements, so the C++ compiler is needed to convert C++ statements into machine instructions. Machine instructions need bits to specify which register(s) they are using; so, with more registers available, more bits in the instructions have to be used to specify the register(s) that the instructions are using.
Susan: Do all the statements change the values of bits they contain depending on the number of registers that are on the CPU?
Steve: Yes, they certainly do. To be more precise, the machine language instructions that execute a statement are larger or smaller depending on the number of registers in the machine, because they need more bits to specify one of a larger number of registers.
Susan: "It takes five bits to select one of 32 items. . ."
". . .and only three bits to select one of eight items." Why?
Steve: What is a bit? It is the amount of information needed to select one of two alternatives. For example, suppose you have to say whether a light is on or off. How many possibilities exist? Two. Since a single bit has two possible states, 0 or 1, we can represent "on" by 1 and "off" by 0 and thus represent the possible states of the light by one bit.
Now suppose that we have a fan that has four settings: low, medium, high, and off. Is one bit enough to specify the current setting of the fan? No, because one bit has only two possible states, while the fan has four. However, if we use two bits, then it will work. We can represent the states by bits as follows:
bits state---- -----
00 off
01 low
10 medium
11 high
Note that this is an arbitrary mapping; there's no reason that it couldn't be like this instead:
bits state---- -----
00 medium
01 high
10 off
11 low
However, having the lowest "speed" (that is, off) represented by the lowest binary value (00) and the increasing speeds corresponding to increasing binary values makes more sense and therefore is easier to remember.
This same process can be extended to represent any number of possibilities. If we have eight registers, for example, we can represent each one by 3 bits, as noted previously in figure registermapfig on page . That is the actual representation in the Intel architecture; however, whatever representation might have been used, it would require 3 bits to select among eight possibilities. The same is true for a machine that has 32 registers, except that you need 5 bits instead of 3.
Susan: Okay, so then does that mean that more than one register can be in use at a time? Wait, where is the room that you are talking about?
Steve: Some instructions specify only one register (a "one-register" instruction), while others specify two (a "two-register" instruction); some don't specify any registers. For example, most "branch" instructions are in the last category; they specify which address to continue execution from. These are used to implement
ifstatements,forloops, and other flow control statements.
Susan: So, when you create an instruction you have to open up enough "room" to talk to all the registers at once?
Steve: No, you have to have enough room to specify any one register, for a one-register instruction, or any two registers for a two-register instruction.
Susan: Well, this still has me confused. If you need to specify only one register at any given time, then why do you always need to have all the room available? Anyway, where is this room? Is it in RAM or is it in the registers themselves? Let's say you are going to specify an instruction that uses only 1 of 32 registers. Are you saying that even though you are going to use just one register you have to make room for all 32?
Steve: The "room" that I'm referring to is the bits in the instruction that specify which register the instruction is using. That is, if there are eight registers and you want to use one of them in an instruction, 3 bits need to be set aside in the instruction to indicate which register you're referring to.
Susan: So you need the bits to represent the address of a register?
Steve: Right. However, don't confuse the "address of a register" with a memory address. They have nothing to do with one another, except that they both specify one of a number of possible places to store information. That is, register
axdoesn't correspond to memory address 0, and so on.
Susan: Yes, I understand the bit numbers in relation to the number of registers.
Steve: That's good.
Susan: So the "address of a register" is just where the CPU can locate the register in the CPU, not an address in RAM. Is that right?
Steve: Right. The address of a register merely specifies which of the registers you're referring to; all of them are in the CPU.
Susan: The registers hold only variables. . . Okay, I know what is bothering me! What else is there besides variables? Besides nonvariables, please don't tell me that. (Actually that would be good, now that I think of it.) But this is where I am having problems. You are talking about data, and a variable is a type of data. I need to know what else is out there so I have something else to compare it with. When you say a register can hold a variable, that is meaningless to me, unless I know what the alternatives are and where they are held.
Steve: What else is there besides variables? Well, there are constants, like the number
5in the statementx = 5;. Constants can also be stored in registers. For example, let's suppose that the variablex, which is ashort, is stored in location 1237. In that case, the statementx = 5;might generate an instruction sequence that looks like this:
mov ax,5
mov [1237],ax
where the number in the [] is the address of the variable
x. The first of these instructions loads5into registerax, and the second one stores the contents ofax(5, in this case) into the memory location1237.Sometimes, however, constants aren't loaded into registers as in this case but are stored in the instructions that use them. This is the case in the following instruction:
add ax,3
This means to add
3to whatever was formerly in registerax. The3never gets into a register but is stored as part of the instruction.39
Another way of reducing overhead is to read instructions from RAM in chunks, rather than one at a time, and feed them into the CPU as it needs them; this is called prefetching. This mechanism operates in parallel with instruction execution, loading instructions from RAM into special dedicated registers in the CPU before they're actually needed; these registers are known collectively as the prefetch queue. Since the prefetching is done by a separate unit in the CPU, the time to do the prefetching doesn't increase the time needed for instruction execution. When the CPU is ready to execute another instruction, it can get it from the prefetch queue almost instantly, rather than having to wait for the slow RAM to provide each instruction. Of course, it does take a small amount of time to retrieve the next instruction from the prefetch queue, but that amount of time is included in the normal instruction execution time.
Susan: I don't understand prefetching. What are "chunks"? I mean I understand what you have written, but I can't visualize this. So, there is just no time used to read an instruction when something is prefetched?
Steve: A separate piece of the CPU does the prefetching at the same time as instructions are being executed, so instructions that have already been fetched are available without delay when the execution unit is ready to "do" them.
The effect of combining the use of registers and prefetching the instructions can be very significant. In our example, if we use an instruction that has already been loaded, which reads data from and writes data only to registers, the timing reduces to that shown in Figure highspeed.
Time Function0 ns Read instruction from RAM40
0 ns Read data from register41
16 ns Execute instruction
0 ns Write result back to register42
-----
16 ns Total instruction execution time
As I indicated near the beginning of this chapter, the manufacturers aren't lying to us; if we design our programs to take advantage of these (and other similar) efficiency measures taken by the manufacturer, we can often approach the maximum theoretical performance figures. You've just been subjected to a barrage of information on how a computer works. Let's go over it again before continuing.
Three main components of the computer are of most significance to programmers: disk, RAM, and the CPU; the first two of these store programs and data that are used by the CPU.
Computers represent pieces of information (or data) as binary digits, universally referred to as bits. Each bit can have the value 0 or 1. The binary system is used instead of the more familiar decimal system because it is much easier to make devices that can store and retrieve 1 of 2 values than 1 of 10. Bits are grouped into sets of eight, called bytes.
The disk uses magnetic recording heads to store and retrieve groups of a few hundred bytes on rapidly spinning platters in a few milliseconds. The contents of the disk are not lost when the power is turned off, so it is suitable for more or less permanent storage of programs and data.
RAM, which is an acronym for Random Access Memory, is used to hold programs and data while they're in use. It is made of millions of microscopic transistors on a piece of silicon called a chip. Each bit is stored using a few of these transistors. RAM does not retain its contents when power is removed, so it is not good for permanent storage. However, any byte in a RAM chip can be accessed in about 70 nanoseconds (billionths of a second), which is hundreds of thousands of times as fast as accessing a disk. Each byte in a RAM chip can be independently stored and retrieved without affecting other bytes, by providing the unique memory address belonging to the byte you want to access.
The CPU (also called the processor) is the active component in the computer. It is also made of millions of microscopic transistors on a chip. The CPU executes programs consisting of instructions stored in RAM, using data also stored in RAM. However, the CPU is so fast that even the typical RAM access time of 70 nanoseconds is a bottleneck; therefore, computer manufacturers have added both external cache and internal cache, which are faster types of memory used to reduce the amount of time that the CPU has to wait. The internal cache resides on the same chip as the CPU and can be accessed without delay. The external cache sits between the CPU and the regular RAM; it's faster than the latter, but not as fast as the internal cache. Finally, a very small part of the on-chip memory is organized as registers, which can be accessed within the normal cycle time of the CPU, thus allowing the fastest possible processing.
In this chapter, we've covered a lot of material on how a computer actually works. As you'll see, this background is essential if you're going to understand what really happens inside a program. In the next chapter, we'll get to the "real thing": how to write a program to make all this hardware do something useful.
1. Hexadecimal arithmetic
a. 48
You probably won't be surprised to hear that Susan didn't care much for this answer originally. Here's the discussion on that topic:
Susan: Problem 1a. My answer is 38. Why? My own personal way of thinking: If a = 10 right? and if e = 14 and if 1 * 10= 10 and if 2 * 14 = 28 then if you add 10 + 28 you get 38. So please inform me how you arrived at 48? I didn't bother with the rest of the problems. If I couldn't get the first one right, then what was the point?
Steve: Here's how you do this problem:
1(1 * 16) + a(10 * 1)
2(2 * 16) + e(14 * 1)
------------------
3(3 * 16) + 18(24 * 1 = 1 * 16 + 8 * 1)
Carry the 1 from the low digit to the high digit of the answer, to produce:
4(4 * 16) + 8(8 * 1), or 48 hex, which is the answer.
b. 2a
c. 3e
2. Binary arithmetic
a. 1011
b. 10000
c. 111
3. 32768 decimal, or 8000 in hex
4. -32768, or 8000 in hex
Why is the same hex value rendered here as -32768, while it was 32768 in question 3? The only difference between short and unsigned short variables is how their values are interpreted. In particular, short variables having values from 8000h to ffffh are considered negative, while unsigned short values in that range are positive. That's why the range of short values is -32768 to +32767, whereas unsigned short variables can range from 0 to 65535.
short. This is no coincidence; read on for the detailed explanation.